백준 28707번

오늘 풀어본 문제는 백준의 28707번 문제¹이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 5

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

길이가 $N$인 양의 정수로 이루어진 배열 $A = [A_1, A_2, \cdots, A_N]$ 이 주어집니다. 이 배열을 비내림차순, 즉, $A_1 \le A_2 \le \cdots \le A_N$ 이 되도록 정렬하기 위해서 다음과 같은 $M$ 가지 조작을 순서와 횟수에 상관 없이 원하는 만큼 할 수 있습니다.

$A$ 의 $l_i$ 번째 수와 $r_i$ 번째 수를 바꿉니다. 비용은 $c_i$ 가 듭니다. $(1 \le i \le M)$ $A$ 를 비내림차순으로 정렬하기 위해 필요한 비용 총합의 최솟값을 출력하세요.

입력

첫 줄에 배열 $A$ 의 길이 $N$ 이 주어집니다. $(2 \le N \le 8)$

둘째 줄에 $A$ 의 각 원소 $A_1, \cdots, A_N$ 이 공백으로 구분되어 주어집니다. $(1 \le A_i \le 10)$

셋째 줄에 조작의 개수 $M$ 이 주어집니다. $(1 \le M \le 10)$

다음 $M$ 개의 줄의 $i$ 번째 줄에 조작을 의미하는 세 개의 정수 $l_i, r_i, c_i$ 가 공백으로 구분되어 주어집니다. $(1 \le l_i < r_i \le N;$ $1 \le c_i \le 10)$

출력

첫 줄에 배열 $A$ 를 비내림차순으로 정렬하기 위해 필요한 비용 총합의 최솟값을 출력하세요. 단, 배열을 비내림차순으로 만드는 것이 불가능한 경우 대신 $-1$ 을 출력하세요.

풀이과정

1번째 시도

주어진 배열을 정렬시키기 위한 방법을 생각해보았는데, 조작이 한정적이라는 점 때문에 뭔가 일반화된 방식같은게 있을 것 같지는 않았다.

대신 이리저리 조작을 해보면서 되는 경우를 찾는 수 밖에 없다는 생각이 들었고, 각 배열의 상태를 노드로, 각 조작을 간선으로, 각 조작의 비용을 간선의 가중치로 설정하여 기존 배열에서 정렬된 배열까지의 ‘최단 경로’ 를 다익스트라 알고리즘을 활용하여 알아내기로 하였다.

코드는 다음과 같이 작성하였다.

#include <bits/extc++.h>

using namespace std;
using namespace __gnu_pbds;

using pii = pair<int, int>;

struct time_based_hash {
	[[gnu::const]] static uint64_t splitmix64(uint64_t x) {
		// http://xorshift.di.unimi.it/splitmix64.c
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}
	
	template <typename T>
    size_t operator()(const std::vector<T>& v) const {
        static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count();
        uint64_t hash = FIXED_RANDOM;

        for (const auto& elem : v) {
            hash ^= std::hash<T>{}(elem) + 0x9e3779b9 + (hash << 6) + (hash >> 2);
        }

        return splitmix64(hash);
    }
};

struct cmp {
    bool operator()(const pair<vector<int>, int>& A, const pair<vector<int>, int>& B) {
        return A.second > B.second;
    }
};

vector<int> applyManipulation(const vector<int>& A, pii manipulation);

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
   
    gp_hash_table<vector<int>, int, time_based_hash> table;
    std::priority_queue<pair<vector<int>, int>, vector<pair<vector<int>, int>>, cmp> pq;
   
    int N;
    cin >> N;
   
    vector<int> A(N);
    for (int i=0; i<N; i++) {
        cin >> A[i];
    }
   
    int M;
    cin >> M;
   
    vector<pair<pii, int>> edges(M);
    for (int i=0; i<M; i++) {
        cin >> edges[i].first.first >> edges[i].first.second >> edges[i].second;
    }
   
    pq.push(make_pair(A, 0));
    table[A] = 0;
    
    while (!pq.empty()) {
        auto curr = pq.top();
        pq.pop();
       
        if (table[curr.first] < curr.second) {
            continue;
        }
        
        for (auto& edge : edges) {
            vector<int> next = applyManipulation(curr.first, edge.first);
           
            if (table.find(next) == table.end() || curr.second + edge.second < table[next]) {
                table[next] = curr.second + edge.second;
                pq.push(make_pair(next, table[next]));
            }
        }
    }
   
    sort(A.begin(), A.end());
   
    if (table.find(A) == table.end()) {
        cout << -1;
    }
    else {
        cout << table[A];
    }
   
    return 0;
}

vector<int> applyManipulation(const vector<int>& A, pii manipulation) {
    vector<int> result = A;
    swap(result[manipulation.first - 1], result[manipulation.second - 1]);
   
    return result;
}

그러자 모든 테스트 케이스를 통과하고 ‘맞았습니다’가 나오는 것을 확인할 수 있었다.

마무리

아이디어가 굉장히 참신한 문제였다! 구현할 요소가 좀 있긴해도 문제를 풀면서 굉장히 즐거웠다.

이 문제를 풀게되면서, CLASS 5 금장을 위해 단 한 개의 문제만이 남게되었다. 끝나는 즉시 CLASS 6 을 향한 여정을 재개하게 될 것 같다.

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/28707

← Previous Post Next Post →